package problema057;

import java.math.BigInteger;

public class SquareRootConvergents {
	
	static int[] numero = new int[1001];
	static BigInteger[] cacheN = new BigInteger[1001];
	static BigInteger[] cacheD = new BigInteger[1001];
	static BigInteger cero = new BigInteger("0");
	static BigInteger diez = new BigInteger("10");
	static BigInteger uno = new BigInteger("1");
	static int res = 0;

	public static void main(String[] args){
		cantNumGrandes();
		System.out.println(res);
	}
	
	public static void cantNumGrandes(){
		llenarVec();
		llenarCache();
		BigInteger num = cero, den = cero;
		for(int i = 1000; i >= 0; i--){
			num = dameNum(i);
			den = dameDen(i);
			if(cumple(num, den)) res++;
		}
	}
	
	public static boolean cumple(BigInteger num, BigInteger den){
		int numL = num.toString().length();
		int denL = den.toString().length();
		if(numL > denL)return true;		
		return false;
	}
	
	public static void llenarCache(){
		for(int i = 0; i < cacheN.length; i++){
			cacheN[i] = cero;
			cacheD[i] = cero;
		}
		cacheN[0] = new BigInteger(Integer.toString(numero[0]));
		int num1 = (numero[0] * numero[1] + 1);
		cacheN[1] = new BigInteger(Integer.toString(num1));
		cacheD[0] = uno;
		cacheD[1] = new BigInteger(Integer.toString(numero[1]));
	}
	
	
	public static BigInteger dameNum(int pos){
		if(!cacheN[pos].equals(cero)) return cacheN[pos];
		BigInteger act = new BigInteger(Integer.toString(numero[pos]));
		cacheN[pos] = act.multiply(dameNum(pos-1)).add(dameNum(pos-2));
		return cacheN[pos];
	}
	
	public static BigInteger dameDen(int pos){
		if(!cacheD[pos].equals(cero)) return cacheD[pos];
		BigInteger act = new BigInteger(Integer.toString(numero[pos]));
		cacheD[pos] = act.multiply(dameDen(pos-1)).add(dameDen(pos-2));
		return cacheD[pos];
	}
	
	public static void llenarVec(){
		numero[0] = 1;
		for(int i = 1; i < numero.length; i++){
			numero[i] = 2;
		}
	}

}
